package com.itheima.leetcode.od.c.tree;

import java.util.Scanner;

/**
 * <h3>计算三叉搜索树的高度</h3>
 */
public class CalculateHeightOfThreewaySearchTree {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入
        int N = scanner.nextInt();
        TernarySearchTree tree = new TernarySearchTree();

        // 构建树
        for (int i = 0; i < N; i++) {
            int num = scanner.nextInt();
            tree.insert(num);
        }

        // 输出树的高度
        System.out.println(tree.getHeight());

        scanner.close();
    }
}

class Node {
    int value;

    Node left, middle, right;

    public Node(int value) {
        this.value = value;
        this.left = null;
        this.middle = null;
        this.right = null;
    }
}

class TernarySearchTree {

    Node root;

    public TernarySearchTree() {
        root = null;
    }

    public void insert(int value) {
        if (root == null) {
            root = new Node(value);
        } else {
            insertRecursive(root, value);
        }
    }

    private void insertRecursive(Node node, int value) {
        if (value < node.value - 500) {  // 规则1：插入左子树
            if (node.left == null) {
                node.left = new Node(value);
            } else {
                insertRecursive(node.left, value);
            }
        } else if (value > node.value + 500) {  // 规则2：插入右子树
            if (node.right == null) {
                node.right = new Node(value);
            } else {
                insertRecursive(node.right, value);
            }
        } else {  // 规则3：插入中子树
            if (node.middle == null) {
                node.middle = new Node(value);
            } else {
                insertRecursive(node.middle, value);
            }
        }
    }

    public int getHeight() {
        return getHeightRecursive(root);
    }

    private int getHeightRecursive(Node node) {
        if (node == null) {
            return 0;
        }

        int leftHeight = getHeightRecursive(node.left);
        int middleHeight = getHeightRecursive(node.middle);
        int rightHeight = getHeightRecursive(node.right);

        return Math.max(Math.max(leftHeight, middleHeight), rightHeight) + 1;
    }
}
